package code.classic150on2025;

import java.util.*;

public class TheGraph {
    // 200. 岛屿数量
    public int numIslands(char[][] grid) {
        // 1 <= m, n <= 300
        int m = grid.length, n = grid[0].length;
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int islands = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '1')
                    continue;
                dfs200(grid, dirs, i, j);
                islands++;
            }
        }
        return islands;
    }

    private void dfs200(char[][] grid, int[][] dirs, int i, int j) {
        grid[i][j] = '2';
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != '1')
                continue;
            dfs200(grid, dirs, x, y);
        }
    }

    // 130. 被围绕的区域
    public void solve(char[][] board) {
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        // 1 <= m, n <= 200
        int m = board.length, n = board[0].length;
        // 先遍历外面一圈，分别dfs，把圈边的O都设为P
        for (int i = 0; i < m; i++) {
            if (i == 0 || i == m - 1) {
                for (int j = 0; j < n; j++) {
                    dfs130(board, i, j, dirs);
                }
            }
            dfs130(board, i, 0, dirs);
            dfs130(board, i, n - 1, dirs);
        }
        // 再把所有的O变为X，所有的P改为O
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == 'P')
                    board[i][j] = 'O';
            }
        }
    }

    private void dfs130(char[][] board, int i, int j, int[][] dirs) {
        if (board[i][j] != 'O')
            return;
        board[i][j] = 'P';
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O')
                continue;
            dfs130(board, x, y, dirs);
        }
    }

    // 133. 克隆图
    public Node cloneGraph(Node node) {
        if (node == null)
            return null;
        Map<Node, Node> map = new HashMap<>();
        return clone133(node, map);
    }

    private Node clone133(Node node, Map<Node, Node> map) {
        if (map.containsKey(node))
            return map.get(node);
        Node copyNode = new Node();
        copyNode.val = node.val;
        copyNode.neighbors = new ArrayList<>();
        map.put(node, copyNode);
        for (int i = 0; i < node.neighbors.size(); i++) {
            Node copyNeighbor = clone133(node.neighbors.get(i), map);
            copyNode.neighbors.add(copyNeighbor);
        }
        return copyNode;
    }

    // 399. 除法求值
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 前置操作，建立编号
        Map<String, Integer> map = new HashMap<>();
        int idx = 0;
        for (List<String> equation : equations) {
            String s1 = equation.get(0);
            String s2 = equation.get(1);
            if (!map.containsKey(s1))
                map.put(s1, idx++);
            if (!map.containsKey(s2))
                map.put(s2, idx++);
        }
        // 构图
        List<GraphEdge399>[] graph = new List[idx];
        for (int i = 0; i < idx; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < equations.size(); i++) {
            int idx1 = map.get(equations.get(i).get(0));
            int idx2 = map.get(equations.get(i).get(1));
            double value = values[i];
            graph[idx1].add(new GraphEdge399(idx2, value));
            graph[idx2].add(new GraphEdge399(idx1, 1 / value));
        }
        // 查询
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String s1 = queries.get(i).get(0);
            String s2 = queries.get(i).get(1);
            if (!map.containsKey(s1) || !map.containsKey(s2)) {
                ans[i] = -1.0;
                continue;
            }
            int start = map.get(s1), end = map.get(s2);
            double[] dist = new double[idx];
            Arrays.fill(dist, -1.0);
            dist[start] = 1.0;
            Deque<Integer> queue = new ArrayDeque<>();
            queue.offer(start);
            while (!queue.isEmpty()) {
                int now = queue.poll();
                for (int j = 0; j < graph[now].size(); j++) {
                    GraphEdge399 edge = graph[now].get(j);
                    if (dist[edge.idx] != -1.0)
                        continue;
                    dist[edge.idx] = dist[now] * edge.len;
                    queue.offer(edge.idx);
                }
            }
            ans[i] = dist[end];
        }
        return ans;
    }

    class GraphEdge399 {
        int idx;
        double len;

        public GraphEdge399(int idx, double len) {
            this.idx = idx;
            this.len = len;
        }
    }

    // 207. 课程表
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        List<Integer>[] to = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            to[i] = new ArrayList<>();
        }
        for (int[] prerequisite : prerequisites) {
            int cNum = prerequisite[0];
            int preNum = prerequisite[1];
            in[cNum]++;
            to[preNum].add(cNum);
        }
        // 查询是否可能
        int count = 0;
        Deque<Integer> zero = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0)
                zero.offer(i);
        }
        while (!zero.isEmpty()) {
            int nowZero = zero.poll();
            count++;
            for (int next : to[nowZero]) {
                in[next]--;
                if (in[next] == 0)
                    zero.offer(next);
            }
        }
        return count == numCourses;
    }

    // 210. 课程表 II
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        List<Integer>[] to = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            to[i] = new ArrayList<>();
        }
        for (int[] prerequisite : prerequisites) {
            int cNum = prerequisite[0];
            int preNum = prerequisite[1];
            in[cNum]++;
            to[preNum].add(cNum);
        }
        // 查询一个序列
        List<Integer> ans = new ArrayList<>();
        int count = 0;
        Deque<Integer> zero = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0)
                zero.offer(i);
        }
        while (!zero.isEmpty()) {
            int nowZero = zero.poll();
            count++;
            ans.add(nowZero);
            for (int next : to[nowZero]) {
                in[next]--;
                if (in[next] == 0)
                    zero.offer(next);
            }
        }
        if (count == numCourses) {
            int[] a = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                a[i] = ans.get(i);
            }
            return a;
        } else {
            return new int[0];
        }
    }

    // 909. 蛇梯棋
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int maxNum = n * n;
        // int[] = {序号，移动数}
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{1, 0});
        // visit表示遍历过，BFS遍历可以找到移动次数最少的路径
        boolean[][] visit = new boolean[n][n];
        int[] pos = snakesGetPos(1, n);
        visit[pos[0]][pos[1]] = true;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            if (poll[0] == maxNum)
                return poll[1];
            for (int i = poll[0] + 1; i <= poll[0] + 6 && i <= maxNum; i++) {
                int nextNum = i;
                int[] newPos = snakesGetPos(nextNum, n);
                if (board[newPos[0]][newPos[1]] != -1) {
                    nextNum = board[newPos[0]][newPos[1]];
                    newPos = snakesGetPos(board[newPos[0]][newPos[1]], n);
                }
                if (visit[newPos[0]][newPos[1]])
                    continue;
                visit[newPos[0]][newPos[1]] = true;
                queue.offer(new int[]{nextNum, poll[1] + 1});
            }
        }
        return -1;
    }

    private int[] snakesGetPos(int num, int n) {
        int i = n - 1 - ((num - 1) / n);
        int j = (n - 1 - i) % 2 == 0 ? (num - 1) % n :(n - 1 - (num - 1) % n);
        return new int[]{i, j};
    }

    // 433. 最小基因变化
    public int minMutation(String startGene, String endGene, String[] bank) {
        // endGene在bank里，如果不在说明不可行
        int num = bank.length;
        List<Integer>[] graph = new List[num];
        Deque<int[]> queue = new ArrayDeque<>();
        boolean[] visit = new boolean[num];
        for (int i = 0; i < num; i++)
            graph[i] = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                if (is2StringConvertable(bank[i], bank[j])) {
                    graph[i].add(j);
                    graph[j].add(i);
                }
            }
        }
        for (int i = 0; i < num; i++) {
            if (is2StringConvertable(startGene, bank[i])) {
                queue.offer(new int[]{i, 1});
                visit[i] = true;
            }
        }
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int number = poll[0], pathNum = poll[1];
            if (bank[number].equals(endGene))
                return pathNum;
            for (int nextNumber : graph[number]) {
                if (visit[nextNumber])
                    continue;
                visit[nextNumber] = true;
                queue.offer(new int[]{nextNumber, pathNum + 1});
            }
        }
        return -1;
    }

    private boolean is2StringConvertable(String a, String b) {
        if (a.length() != b.length())
            return false;
        int len = a.length();
        int diffCount = 0;
        for (int i = 0; i < len; i++) {
            if (a.charAt(i) != b.charAt(i))
                diffCount++;
            if (diffCount > 1)
                return false;
        }
        return diffCount == 1;
    }

    // 127. 单词接龙
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int n = wordList.size();
        Deque<int[]> queue = new ArrayDeque<>();
        List<Integer>[] graph = new List[n];
        boolean[] visit = new boolean[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!isNeighbor(wordList.get(i), wordList.get(j)))
                    continue;
                graph[i].add(j);
                graph[j].add(i);
            }
        }
        for (int i = 0; i < n; i++) {
            if (!isNeighbor(wordList.get(i), beginWord))
                continue;
            queue.offer(new int[]{i, 2});
            visit[i] = true;
        }
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int num = poll[0], pathNum = poll[1];
            if (wordList.get(num).equals(endWord))
                return pathNum;
            for (int next : graph[num]) {
                if (visit[next])
                    continue;
                queue.offer(new int[]{next, pathNum + 1});
                visit[next] = true;
            }
        }
        return 0;
    }

    private boolean isNeighbor(String s1, String s2) {
        int len = s1.length();
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (s1.charAt(i) != s2.charAt(i))
                count++;
            if (count > 1)
                return false;
        }
        return count == 1;
    }
}

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}